A decentralized computing environment may be defined by a number of computing systems interconnected to communicate with one another, wherein each computing system can perform both client and server functions. A peer-to-peer (P2P) network represents a decentralized computing environment in which each computing system within the P2P network is defined as a peer of every other computing system within the network. For discussion purposes, each peer computing system within the P2P network is referred to as a node. Additionally, each node within the P2P network may be configured to execute software having substantially equivalent functionality. Therefore, each node may act as both a provider and a user of data and services across the P2P network. Peer to peer networks are distributed data networks without any centralized hierarchy or organization. Peer to peer data networks provide a robust and flexible means of communicating information between large numbers of computers or other information devices, referred to in general as nodes.
A P2P network relies primarily on the computing power and bandwidth of the participants in the network rather than concentrating it in a relatively low number of servers. P2P networks are typically used for connecting nodes via largely ad hoc connections. Such networks are useful for many purposes. P2P networks may be used, e.g., for sharing content files containing audio, video, data or anything in digital format is very common, and real-time data, such as telephony traffic, may also be transmitted using P2P technology.
An overlay network is a logical or virtual network organization that is imposed on nodes connected by one or more types of underlying physical network connections. In an overlay network, nodes are connected by virtual or logical links, each of which can correspond with one or more paths in an underlying physical network. Overlay network are typically implemented in hardware and/or software operating in the application layer or other top-level layer of an OSI network stack or other type of networking protocol.
One class of peer to peer overlay networks are referred to as distributed hash table networks. Distributed hash table overlay networks use a hash function to generate and assign one or more key values to a unique node. The set of all possible key values is referred to as a hash space. Nodes are organized in the hash space according to their assigned key values. The hash function is selected so that nodes are approximately evenly distributed throughout the hash space. Distributed hash table overlay networks are typically highly scalable, often supporting millions of nodes; robust, allowing nodes to join or leave frequently; and efficient, routing a message to a single destination node quickly.
There are numerous different types of distributed hash table overlay networks. One type of peer to peer overlay network is known as a Chord network. The Chord overlay network protocol is described in detail in “Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications”, Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan, IEEE/ACM Transactions on Networking, Vol. 11, No. 1, pp. 17-32, February 2003, which is incorporated herein by reference. Another type of distributed hash table overlay network is Pastry, which is described in “Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems,” A. Rowstron and P. Druschel. IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Germany, pages 329-350, November, 2001, which is incorporated herein by reference.
A Chord overlay network may exhibit logarithmic properties arising from “asymptotic complexity” of messaging. For example, if there are N nodes in a Chord ring and a first node wants to send a message to a second node, the first node typically has to communication with some subset of the N nodes in order to locate node B. In a Chord overlay network, the first node generally has to communicate with a very small subset of all N nodes, specifically log2 N. This property allows a Chord overlay network to have relatively fast messaging, even for a very large number N of nodes. However, a Chord overlay network can only guarantee this log2 N messaging property if the IDs of the nodes are completely randomly distributed around the Chord ring.
Current state of the art Chord overlay networks often rely on an even, random distribution of the node IDs in distributed hash tables to provide load balanced routing of queries and messages in a peer to peer network. However, even if node IDs are evenly and randomly distributed clustering of recipients of a message or query within the global address space of the P2P network may lead to bottlenecks. For example, when a peer tries to route the same message to multiple peer nodes, some intermediate nodes may become overloaded as they route messages if those nodes are responsible for the address space of the recipients.
It is within this context that embodiments of the present invention arise.